package com.lw.leetcode.tree.c;

import com.lw.test.util.Utils;

import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 315. 计算右侧小于当前元素的个数
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/6 16:42
 */
public class CountSmaller {

    public static void main(String[] args) {
        CountSmaller test = new CountSmaller();

        // [2,1,1,0]
//        int[] arr = {5, 2, 6, 1};

        // [0]
//        int[] arr = {-1};

        // [0, 0]
//        int[] arr = {-1, -1};

        // [1, 0, 0]
//        int[] arr = {8647, 5216, 9515};

        // [0, 0]
        int[] arr = Utils.getArr(100000, -10000, 10000);

        List<Integer> list = test.countSmaller(arr);
        System.out.println(list);
    }

    private Node root;

    public List<Integer> countSmaller(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        root = new Node(min, max);
        int length = nums.length;
        Integer[] arr = new Integer[length];
        for (int i = length - 1; i >= 0; i--) {
            add(root, nums[i]);
            arr[i] = find(root, nums[i]);
        }
        return Arrays.asList(arr);
    }

    private int find(Node node, int value) {
        int st = node.st;
        int end = node.end;
        if (st == end) {
            return 0;
        }
        int m = st + ((end - st) >> 1);
        if (value <= m) {
            return find(node.left, value);
        } else {
            return find(node.right, value) + (node.left == null ? 0 : node.left.count) ;
        }
    }

    private void add(Node node, int value) {
        int st = node.st;
        int end = node.end;
        if (st == end) {
            node.count++;
            return;
        }
        int m = st + ((end - st) >> 1);
        if (value <= m) {
            if (node.left == null) {
                node.left = new Node(st, m);
            }
            add(node.left, value);
        } else {
            if (node.right == null) {
                node.right = new Node(m + 1, end);
            }
            add(node.right, value);
        }
        node.count++;
    }

    private static class Node {
        private int st;
        private int end;
        private int count;
        private Node left;
        private Node right;

        private Node(int st, int end) {
            this.st = st;
            this.end = end;
        }
    }

}
